用于线速网络功能的可编程多维表滤波器

0 摘要

基于状态资源特定指标的多维策略，进行数据过滤的能力十分关键。

当前一代的可编程交换机不支持线性速度的表范围状态过滤。

我们推出了 Thanos，它通过支持对一组资源的可编程多维过滤来增强现有的可编程开关管道。

Thanos 以标称芯片面积开销与多太比特可编程交换机管道无缝集成。

我们基于 FPGA 原型和模拟器的评估表明，与最先进的技术相比，Thanos 中表达的策略可以将关键网络功能的性能提高高达 1.7 倍。

1 introduction

可编程交换机的出现使网络交换机变得越来越有状态，因为交换机现在能够存储大量有状态指标（例如路径上的拥塞情况、端口的排队统计数据、流的数据包计数器），以便在以下情况下做出智能决策：数据平面涉及关键网络功能，例如路由、负载平衡、拥塞控制、网络诊断、故障下的策​​略合规性以及安全性和安全性。

核心是资源过滤能力，包括性能感知路由、拥塞感知负载平衡、有状态的 L4 负载均衡、数据平面诊断、安全和防火墙、政策合规性。

上面提到的所有策略都可以抽象为一系列过滤操作，过滤标准可以是无状态的（选择随机资源），也可以使用有状态资源特定指标来过滤所需的资源。

过滤器操作也可以链接起来，其中一个过滤器操作的输出用作下一个过滤器操作的输入

然而不幸的是，当前一代的可编程交换机由于其有限的内存和计算语义而无法以线速表达上述过滤策略

我们推出了 Thanos，它是一种增强的可编程交换机架构，能够以线速在一组资源上表达丰富的多维过滤策略。 Thanos 使用用于链式多维过滤的新硬件模块扩展了当前的可编程开关管道，即可重新配置匹配表（RMT）

2 motivation

2.1 数据平面中线路速率过滤的需要

2.2 RMT 的局限性

Reconfigurable Match Table 即可重新配置的匹配表。通过 match tables 匹配表和 Register arrays 寄存器数组实现过滤。

匹配表

具有多个属性，对应数据包头字段，匹配并过滤。匹配类型是精确匹配（SRAM）或三元匹配（TCAM）。但是，匹配表无法根据自定义过滤策略过滤表中的条目。

寄存器数组

可以实现数据结构，如哈希表。我们可以将资源及其有状态度量存储在寄存器哈希表中，并以线速实现简单的无状态过滤策略，例如随机选择资源。

当涉及到基于状态过滤标准来过滤资源时，例如过滤具有最小度量值的资源或过滤具有度量值 < x 的所有资源，寄存器数组就无法满足需要。这是因为 RMT 允许每个流水线阶段（每个时钟周期）每个数据包访问每个寄存器阵列的最多单个条目。需要 O (N ) 个时钟周期或流水线级来迭代单个滤波器操作的一组资源，其中 N 是资源数量，从而排除了线速处理。

通过尝试使用寄存器数组（例如已知对多种过滤操作有效的 B 树 ）实现更复杂的数据结构，可以潜在地提高过滤操作的时间复杂度。直接的实现会将 B 树中的每个节点存储在寄存器中，并将 B 树的每个级别映射到 RMT 中的不同管道阶段。但即便如此，在 RMT 中也很难实现，因为 RMT 管道是前馈的，即数据包和状态只能通过管道向前移动。因此，一旦树的第 i 层节点遍历到 >i 层，就无法返回并更新它们，而这在 B 树实现中是需要的。从阶段 i+1 访问阶段 i 状态的一种可能的解决方法是让数据包通过管道向前移动直到最后一个阶段，然后将数据包重新循环到管道的开头以最终到达阶段 i 。但这会有效地降低交换机的数据包处理吞吐量，同时还会带来高延迟损失。

在本文中，我们提出了使用用于多维过滤的新硬件模块来增强 RMT 的案例，该模块可以轻松地与 RMT 管道集成，并且有可能改进几个关键网络功能，包括路由、负载均衡、网络诊断和防火墙，甚至某些关键的分布式应用，例如关系数据库和图数据库查询。

3 系统架构

过滤器模块与 RMT 管道的匹配操作阶段内联集成，可以将多个此类过滤器模块与 RMT 管道集成，其中每个模块将表达针对一组不同资源的过滤器策略。

过滤操作的输出被写入数据包的元数据中，以便在过滤器模块之后的 RMT 阶段中进行进一步处理。过滤器模块是完全流水线的，因此可以在每个时钟周期提供新的数据包。

对一组资源实施过滤策略涉及四个关键任务：

1.计算资源指标的值

资源指标远程生成：路径上的拥塞、Web 服务器上的资源消耗。对于远程生成的指标，依赖 probe packets 携带信息。此外，依赖 RMT 管道处理探测数据包并提取度量信息。

资源指标本地生成：数据包计数器、交换机端口处的排队。依赖 RMT 原语来计算简单的本地指标。对于更复杂的指标，例如涉及流量管理器的指标，利用最近提出的 RMT 事件驱动数据包处理架构，允许自定义事件以线速出发 RMT 管道内的自定义处理。如每次数据包进入队列，会递增寄存器数值，出队列的时候会递减寄存器值，因此，人们可以轻松地以线速度维护队列的长度。

2.存储资源和指标

要设计一个数据结构存储资源及其各自的指标，要求允许以线速实施丰富的过滤策略。提出了一种新的硬件数据结构。

3.实施过滤策略

提出了一个新的自定义过滤管道和定制的操作单元。

4.处理过滤的输出

涉及到转发、删除数据包，因此将此最终任务映射到 RMT 管道。

4. 抽象和原语

资源及其相应的指标可以表示为关系表，并且过滤策略可以简化为关系表上的过滤操作链。给定 N 个资源，每个资源都有 M 个指标，Thanos 将资源存储在一个具有 N 个条目和 M+1 个属性的全局关系表中

4.1 基础过滤运算符

支持两类过滤运算符：(i) 一元运算符，基于零个或一个表属性进行过滤；(ii) 二元运算符，合并两个一元过滤运算的输出以支持多维过滤。

4.1.1 一元过滤运算符。

将单个关系表用作输入，至多一个表属性进行过滤并返回行（我的理解：类似数据库表单个属性过滤）

一般的网络中，过滤操作有三种：（1）基于对某属性的 predicate（谓词）（2）基于对属性的排序（3）随机操作

Thanos 借用并扩展了 Codd 关系代数中的经典一元运算符，提出以下 5 个运算符：（1）不操作.（2）谓词操作包括大于、小于、不等于、等于（3）min/max（4）根据权重列表排序（5）随机输出

4.2.2 二元操作运算符

将两个关系表作为输入，不包括 join，因为 Thanos 有一个全局关系表，不需要 join。

包括以下 4 个运算符：（1) 选择一个表输出。（2）输出两个表的和（3）输出两个表的共有条目（4）输出在表一但不在表二的条目。

4.2 过滤器链的抽象

链接运算符表达更丰富的过滤策略。

4.2.1 并行链接

由 k 个一元运算符构成。一次选出一些作为结果，之后从剩下的里面再选一些，之后从剩下的里面再选一些，直到结束过滤，把所有筛选结果合并。

4.2.2 串行链接

适用于一元和二元运算符，输入 n 个关系表，输出 m 个关系表。

编了一大堆很牛逼的话，总结，可以拓扑排序，有向无环图。

4.2.3 条件策略

可以用嗯并行或串行来表达如果（条件），那么（策略一），不然（策略二）。通过并行或串行来表达策略一和策略二，在最后通过 MUX 根据谓词在策略的输出中进行选择，MUX 可以在单个 RMT 管道阶段中实现，该阶段在 Thanos 过滤器模块之后。

5 硬件设计

就是 design 的中间的两个模块。

希望是完全流水线设计，每个时钟周期处理一个新的数据包，产生确定性的延迟，确保线路速率与 RMT 管道速率相匹配。

5.1 资源表

使用名为排序多维双向映射 (SMBM) 的新硬件数据结构将资源表存储为关系表。SMBM 维护资源 id 和每个指标的双向映射，维护每个指标的升序排序。

5.1.1 为什么是 smbm

对新数据结构的需求，源于传统过滤数据结构的两个关键限制。1.缺乏通用数据结构。2.经典数据结构的性能限制。如果采用树形结构，会导致 logN 的复杂度。从根本上来说，经典数据结构是为类似 CPU 的架构而设计的，无法充分利用定制硬件上可用的空间并行性。

5.1.2 smbm 的执行

SMBM 包含 M+1 个排序列表，排序列表的实现基于 PIFO 中描述的设计，其中 N 个元素存储在 N 端口存储器中，通常使用 N 个触发器来实现。